
/*
 * Problem: 可重集合排列
 * Author: Yuanshun L
 * Created: 9-Nov-2021
 * Method: 枚举法
 */

#include<iostream>
#include<algorithm>

using namespace std;
const int n = 6;
int target[] = {1,5,1,3,4,2};
int cnt = 0;

void permutation(int *t, int *a, int m){
    if(m == n){
        // 打印一个全排列
        cnt++;
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    else{
        // 找出所有可能在m出放置的数
        for(int i=0;i<n;i++){
            if(i == 0 ||  t[i] != t[i-1]){
                int n1=0,n2=0;
                // t[i] 已经填写的次数
                for(int j=0;j<m;j++)  if(a[j] == t[i]) n1++;
                // t[i] 在数集中出现的总数
                for(int j=0;j<n;j++)  if(t[j] == t[i]) n2++;
                if(n2 > n1){
                    a[m] = t[i];
                    permutation(t,a,m+1);
                }
            }
        }
    }
}

int main(){

    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);

    int a[n];
    sort(target,target+n);

    permutation(target,a,0);
    cout<< "The Number of Possibility :"<<cnt<<endl;
    return 0;
}